// 从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。

 



#include<bits/stdc++.h>
using namespace std;

// 广度遍历，使用队列模拟

// 执行用时：
// 8 ms
// , 在所有 C++ 提交中击败了
// 29.76%
// 的用户
// 内存消耗：
// 13.3 MB
// , 在所有 C++ 提交中击败了
// 5.04%
// 的用户


 struct TreeNode {
     int val;
     TreeNode *left;
     TreeNode *right;
     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 };

class Solution {
public:
    queue<TreeNode*> que;
    vector<vector<int>> res;
    vector<vector<int>> levelOrder(TreeNode* root) {
        if(root==nullptr){
            return res;
        }
        que.push(root);
        bfs();
        return res;
    }

    void bfs(){
        while(!que.empty()){
            queue<TreeNode*> que_temp;
            while(!que.empty()){
                que_temp.push(que.front());
                que.pop();
            }
            vector<int> vec;
            while(!que_temp.empty()){
                vec.emplace_back(que_temp.front()->val);
                if(que_temp.front()->left!=nullptr){
                    que.push(que_temp.front()->left);
                }
                if(que_temp.front()->right!=nullptr){
                    que.push(que_temp.front()->right);
                }
                que_temp.pop();
            }
            res.emplace_back(vec);
        }
    }
};